Skip to main content

622. Design Circular Queue

문제

Design your implementation of the circular queue. The circular queue is a linear data structure in which the operations are performed based on FIFO (First In First Out) principle, and the last position is connected back to the first position to make a circle. It is also called "Ring Buffer".

One of the benefits of the circular queue is that we can make use of the spaces in front of the queue. In a normal queue, once the queue becomes full, we cannot insert the next element even if there is a space in front of the queue. But using the circular queue, we can use the space to store new values.

Implement the MyCircularQueue class:

  • MyCircularQueue(k) Initializes the object with the size of the queue to be k.
  • int Front() Gets the front item from the queue. If the queue is empty, return -1.
  • int Rear() Gets the last item from the queue. If the queue is empty, return -1.
  • boolean enQueue(int value) Inserts an element into the circular queue. Return true if the operation is successful.
  • boolean deQueue() Deletes an element from the circular queue. Return true if the operation is successful.
  • boolean isEmpty() Checks whether the circular queue is empty or not. boolean isFull() Checks whether the circular queue is full or not. You must solve the problem without using the built-in queue data structure in your programming language.

예제 입출력

Input
["MyCircularQueue", "enQueue", "enQueue", "enQueue", "enQueue", "Rear", "isFull", "deQueue", "enQueue", "Rear"]
[[3], [1], [2], [3], [4], [], [], [], [4], []]
Output
[null, true, true, true, false, 3, true, true, true, 4]

Explanation
MyCircularQueue myCircularQueue = new MyCircularQueue(3);
myCircularQueue.enQueue(1); // return True
myCircularQueue.enQueue(2); // return True
myCircularQueue.enQueue(3); // return True
myCircularQueue.enQueue(4); // return False
myCircularQueue.Rear(); // return 3
myCircularQueue.isFull(); // return True
myCircularQueue.deQueue(); // return True
myCircularQueue.enQueue(4); // return True
myCircularQueue.Rear(); // return 4

info

You can read the full description here.

풀이 1

접근법

  1. 배열을 이용합니다. k+1 개의 공간을 이용합니다.
  2. 인덱스 front와 rear를 관리합니다. front는 첫 원소를, rear는 맨 마지막 원소 다음 공간을 가리키도록 합니다.

참고용 그림

image-20230109212530607

구현 코드

class MyCircularQueue:

def __init__(self, k: int):
self.queue = [-1 for _ in range(k + 1)]
self.front = 0
self.rear = 0
self.size = k + 1

def enQueue(self, value: int) -> bool:
if self.isFull():
return False
else:
self.queue[self.rear] = value
self.rear = (self.rear + 1) % self.size
return True

def deQueue(self) -> bool:
if self.isEmpty():
return False
else:
self.front = (self.front + 1) % self.size
return True

def Front(self) -> int:
if self.isEmpty():
return -1
else:
return self.queue[self.front]

def Rear(self) -> int:
if self.isEmpty():
return -1
else:
return self.queue[((self.rear - 1) + self.size) % self.size]

def isEmpty(self) -> bool:
return self.front == self.rear

def isFull(self) -> bool:
return (self.rear + 1) % self.size == self.front

책에 있는 풀이

info

원본 코드는 여기에서 확인하실 수 있습니다.


풀이 2

접근법

  1. Front, Rear는 Full 과 Empty 상태가 동일해서 None 인지 여부를 한 번 더 확인해주어야 합니다.

참고용 그림

image-20230109211535859

구현 코드

class MyCircularQueue:
def __init__(self, k: int):
self.q = [None] * k
self.maxlen = k
self.p1 = 0
self.p2 = 0

# enQueue(): 리어 포인터 이동
def enQueue(self, value: int) -> bool:
if self.q[self.p2] is None:
self.q[self.p2] = value
self.p2 = (self.p2 + 1) % self.maxlen
return True
else:
return False

# deQueue(): 프론트 포인터 이동
def deQueue(self) -> bool:
if self.q[self.p1] is None:
return False
else:
self.q[self.p1] = None
self.p1 = (self.p1 + 1) % self.maxlen
return True

def Front(self) -> int:
return -1 if self.q[self.p1] is None else self.q[self.p1]

def Rear(self) -> int:
return -1 if self.q[self.p2 - 1] is None else self.q[self.p2 - 1]

def isEmpty(self) -> bool:
return self.p1 == self.p2 and self.q[self.p1] is None

def isFull(self) -> bool:
return self.p1 == self.p2 and self.q[self.p1] is not None